/*
Problem Description
有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。
Input
第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。
Output
输出对应的c，每组测试数据占一行。
Sample Input
2
6 2
12 4
Sample Output
4
8
 */
package com.yuan.algorithms.practice201512;

import java.util.Scanner;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年12月5日 下午12:20:47
 * <br>说明:从c=2*b开始向后搜索，每次递增b，直到a和c的最大公约数为b。
 */
public class 又见GCD {
	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		while(in.hasNext()) {
			int n = in.nextInt();
			while(n-- > 0) {
				int a = in.nextInt();
				int b = in.nextInt();
				int c = b * 2;
				while(gcd(a, c) != b) {
					c += b;
				}
				System.out.println(c);
			}
		}
	}
	private static int gcd(int a, int b) {
		return a == 0 ? b : gcd(b%a, a);
	}
}
